# 307 中等：区域和检索-数组可修改
from typing import List


class NumArray:

    # # 严重超时
    # def __init__(self, nums: []):
    #     self.nums = nums
    #
    # def update(self, index: int, val: int) -> None:
    #     self.nums[index] = val
    #
    # def sumRange(self, left: int, right: int) -> int:
    #     return sum(self.nums[left:right+1])
    #     # ret = 0
    #     # for i in range(left, right + 1):
    #     #     ret += self.nums[i]
    #     # return ret

    # 线段树
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.n = n
        self.seg = [0] * (n << 2)
        self.build(nums, 0, n - 1, 1)

    def build(self, nums, l, r, rt):
        if l == r:
            self.seg[rt] = nums[l]
            return
        mid = l + (r - l) // 2
        self.build(nums, l, mid, rt << 1)
        self.build(nums, mid + 1, r, rt << 1 | 1)
        self.seg[rt] = self.seg[rt << 1] + self.seg[rt << 1 | 1]

    def change(self, index, val, l, r, rt):
        if l == r:
            self.seg[rt] = val
            return
        mid = l + (r - l) // 2
        if index <= mid:
            self.change(index, val, l, mid, rt << 1)
        else:
            self.change(index, val, mid + 1, r, rt << 1 | 1)
        self.seg[rt] = self.seg[rt << 1] + self.seg[rt << 1 | 1]

    def query(self, L, R, l, r, rt):
        if L <= l and R >= r:
            return self.seg[rt]
        mid = l + (r - l) // 2
        if L > mid:
            return self.query(L, R, mid + 1, r, rt << 1 | 1)
        if R <= mid:
            return self.query(L, R, l, mid, rt << 1)
        return self.query(L, R, l, mid, rt << 1) + self.query(L, R, mid + 1, r, rt << 1 | 1)

    def update(self, index: int, val: int) -> None:
        return self.change(index, val, 0, self.n - 1, 1)

    def sumRange(self, left: int, right: int) -> int:
        return self.query(left, right, 0, self.n - 1, 1)
